FIG. 1 illustrates a structure of a mobile communication channel to which the present invention and the related art are applied. Hereinafter, the structure of the mobile communication channel will be described with reference to FIG. 1. A transmitter undergoes a channel coding procedure to transmit data without loss or distortion through a wireless channel. Examples of the channel coding include convolutional coding, turbo coding, LDPC coding, etc. The data which has undergone the channel coding procedure can be transmitted to the wireless channel as a single symbol which includes several bits. At this time, a procedure of mapping several bits to a single symbol is referred to as modulation.
The modulated data is converted into a signal for multiple transmission through a multiplexing procedure or a multiple access method. Examples of the multiplexing procedure include CDM, TDM, FDM, etc. The signal which has undergone the multiplexing block is changed to a structure suitable for transmission to one or more multi-antennas, and then is transferred to a receiver through the wireless channel. Fading and thermal noise occur in the transmitted data when the data passes through the wireless channel. For this reason, distortion may occur in the data.
The modulated data is transferred to the receiver through the wireless channel. In this case, fading and thermal noise occur in the transmitted data, whereby distortion may occur therein. The receiver performs a series of procedures of the transmitter in reverse order after receiving the distorted data. The receiver performs demodulation to convert the data mapped to the symbol into a bit stream, undergoes channel decoding, and recovers the distorted data to the original data.
An apparatus of performing the channel coding stores a matrix H or a generation matrix G, wherein the matrix H is a parity check matrix used to generate parity bits to be added to input data (information bits or systematic bits), and the generation matrix G is derived from the matrix H. In other words, the transmitter includes an encoder which generates parity bits through the input data and the matrix H or G. An apparatus of performing channel decoding checks whether the systematic bits are recovered well, through operation of the received data (distorted systematic bits+parity bits) with the matrix H, and performs operation again if the systematic bits are failed to be recovered.
Examples of the modulation include BPSK (Binary Phase Shift Keying), QPSK (Quadrature Phase Shift Keying), 16-QAM (Quadrature Amplitude Modulation), 64-QAM, 256-QAM, etc. For example, 16-QAM maps the data stream which has undergone channel encoding during modulation to a single symbol in a unit of 4 bits. 16-QAM de-maps the single symbol received through the wireless channel during demodulation to four bits.
Hereinafter, a data retransmission scheme that can be used along with the embodiments of the present invention will be described. There are provided various examples of the data retransmission scheme. Of them, HARQ (Hybrid Automatic Repeat reQuest) scheme will be described below. The HARQ scheme is obtained by combination of FEC (Forward Error Correction) symbol and ARQ (Automatic Repeat reQuest) which is a retransmission scheme in a mobile communication system. According to the ARQ scheme, if an error is detected from data received by the receiver, the receiver requests the transmitter to perform retransmission. Examples of the ARQ scheme include Stop-And-Wait, Selective Repeat, Go-Back-N, etc. depending on the retransmission method.
According to the Stop-And-Wait method, as shown in FIG. 2, if the transmitter receives an acknowledgement (ACK) message from the receiver after transmitting data, the transmitter transmits next data, wherein the ACK message notifies that the receiver has successfully received the data. If the transmitter receives a NACK message from the receiver, wherein the NACK message notifies that the receiver has failed to successfully receive the data, the transmitter retransmits the failed data.
Meanwhile, according to the Go-Back-N method, the transmitter first transmits N number of data and receives ACK messages from the receiver in due order. FIG. 3 illustrates a case of N=7, wherein the number N of data which are transmitted without ACK message is referred to as a window size. If the transmitter receives the NACK message in response to the kth data, the transmitter sequentially transmits data starting from the kth data.
FIG. 4 illustrates a Selective Repeat method. According to the Selective Repeat method, like the Go-Back-N method, the number N of data which are transmitted without ACK or NACK message is referred to as a window size, and retransmission is selectively performed for only data with NACK message.
According to the aforementioned HARQ method, if retransmission is performed in the ARQ method, previously transmitted data is combined with retransmitted data to restore the data through FEC symbol. The HARQ method is classified into a chase combining method and an incremental redundancy method depending on a combining method of the two data. According to the chase combining method, as shown in FIG. 5, the receiver combines transmission data with retransmission data to increase a receiving signal to noise ratio (SNR), thereby increasing a receiving success ratio of data at the receiver.
Meanwhile, unlike the chase combining method, the incremental redundancy method (hereinafter, referred to as ‘IR method’) transmits some of encoded data, which have not been used for first transmission, during retransmission of the transmitter to decrease a coding rate of data received at the receiver, thereby increasing a receiving success ratio.
Hereinafter, LDPC coding will be described. A concept of LDPC coding is as follows.
A linear code can be described with the generation matrix G or the parity check matrix H. A characteristic of the linear code is that the equation of HcT=0 is satisfied for every bit of a codeword ‘c’. As one of the linear code, the LDPC code which is recently paid attention to was proposed by Gallager in 1962 for the first time. One of the characteristics of the LDPC coding is that most of elements of the parity check matrix H are ‘0 ’ and the number of elements which are not ‘0 ’ is small compared to the codeword, so that repetitive decoding based on probability is possible. A parity check matrix H for the first proposed LDPC code was defined in a non-systematic form and each row and column of the parity check matrix were designed to equally have a small weight.
In this case, the weight means the number of ‘1 ’ included in each row and column.
The LDPC coding scheme has low decoding complexity since a density of elements which are not ‘0’ on the parity check matrix H is low. Further, decoding performance of the LDPC coding is superior to other coding schemes, which is adjacent to the theoretical limit of Shannon. However, the LDPC coding scheme could not be implemented with the hardware technique at the time of proposal by Gallager, so that the LDPC coding scheme has not been paid attention to by the people for 30 years. A repetitive decoding scheme using graphs was developed in early 1980's and a couple of decoding algorithms for the LDPC code have been developed using the repetitive decoding scheme. One of them is a sum-product algorithm.
Hereinafter, features of the LDPC coding will be described. The LDPC coding has a superior error correction capability, thereby improving communication speed and capacity. When combined with a multi-input and multi-output (MIMO) scheme, the LDPC coding can be applied to a high speed wireless LAN having a data transmission speed of several hundred Mbit/s, a high speed mobile communication system having a data transmission speed of one Mbit/s or greater for a user moving at a speed of 250 km/h, and an optical communication system having a data transmission speed of 40 Gbit/s or greater. In addition, the LDPC coding can enable quantum encryption communication diminishing the number of retransmission times on a communication path having low quality since transmission quality is improved due to its high error correction capability. Further, data packets having errors can be easily recovered due to the low complexity and superior loss compensation capability of the LDPC coding, so that contents having quality equal to that of TV can be transmitted through the Internet and the mobile communication system. 10G BASE-T transmission within a range of 100 m which has been considered impossible earlier can be realized owing to wide application range and large capacity which are advantages of the LDPC coding. In addition, transmission capacity of a single satellite transmitter having 36 MHz bandwidth can be increased up to 80 Mbit/s which is 1.3 times of usual transmission capacity.
According to a general LDPC encoding method, information bits are encoded by using a generation matrix G derived from an LDPC parity check matrix H. In order to derive the generation matrix G, the parity check matrix H is configured in the form of [PT: I] by using a Gaussian reduction method. Assuming the number of the information bits is ‘k’ and a size of an encoded codeword is ‘n’, the ‘P’ is a matrix having ‘k’ number of rows and ‘(n−k)’ number of columns and the ‘I’ is an identity matrix having ‘k’ number of rows and columns.
When the parity check matrix H is represented in the form of [PT: I], the generation matrix G has the form of [I: P]. The information bits of k bits to be encoded can be represented as a matrix ‘x’ having one row and ‘k’ number of columns. In this case, the codeword ‘c’ is represented in the form of the following equation.c=xG=[x:xP]  [Equation 1]
In the above equation, x represents an information part (or a systematic part), and xP represents a parity part.
An LDPC decoding method according to the related art will be described. A matrix Hsys is derived from a LDPC parity check matrix H, and a matrix Gsys is derived from the matrix Hsys, whereby encoding is performed. In this case, the matrix Hsys is obtained by configuring one part of the parity check matrix H in a systematic type through row operation. The matrixes Hsys and Gsys can be expressed by the following equations 2 and 3.Hsys=[P:In-k]  [Equation 2]Gsys=[Ik:−PT]  [Equation 3]
Data encoded in a communication system includes noise when passing through a wireless channel of FIG. 1. A receiver represents a decoding procedure of data through a procedure as shown in FIG. 8. A decoding block of the receiver obtains an information bit ‘x’ from a receiving signal c′ having the encoded codeword ‘c’ added with noise by using the feature of cHT=0. In other words, assuming that the received codeword is c′, a value of c′HT is calculated. As a result, if the value of c′HT is 0, first k number of bits from c′ are determined as the information bit x. If the value of c′HT is not 0, c′ which satisfies c′HT of 0 is searched by using a decoding method such as a sum-product algorithm through a graph, thereby restoring the information bit x.
Hereinafter, a coding rate of LDPC coding will be described.
Generally, when the size of the information bit is k and the size of the codeword which is actually transmitted is n, a coding rate (R) is as follows.R=k/n  [Equation 4]
When the matrix H necessary for LDPC encoding and decoding has a row size of m and a column size of n, a coding rate is as follows.R=1−m/n  [Equation 5]
As described above, since the related art LDPC code is encoded and decoded by the matrix H, the structure of the matrix H is very important. In other words, since encoding and decoding performance is greatly affected by the structure of the matrix H, design of the matrix H is more important than anything else.
In the LDPC decoding method according to the related art, complex matrix operation is required when the matrixes Hsys and Gsys are generated from the parity check matrix. Particularly, a problem occurs in that resources required for the operation also increase as the size of the parity check matrix increases, whereby complexity of the overall system is increased.